package com.mdnote.practice.dp;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/23
 * @description
 */
public class LeetCode647 {


    public static void main(String[] args) {
        LeetCode647 leetCode647 = new LeetCode647();
        System.out.println(leetCode647.countSubstrings("abcdcba"));

    }
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // 中心扩展发
//        return center(s);
        // 动态规划
        return dp(s);
    }

    private int center(String s) {

        int centerLeft = 0, centerRight = 0;
        int count = 0;
        for (int center = 0; center < s.length() * 2 - 1; center++) {
            centerLeft = center / 2;
            centerRight = center / 2 + (center & 1);

            while (centerLeft >= 0 && centerRight < s.length() && s.charAt(centerLeft) == s.charAt(centerRight)) {
                centerLeft--;
                centerRight++;
                count++;
            }
        }

        return count;
    }

    private int dp(String s) {

        boolean[][] dp = new boolean[s.length()][s.length()];

        int count = 0;

        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j) && ((i - j <2) || dp[i - 1][j + 1])) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }

        return count;
    }
}
